package leetcode;

public class LeetCode81 {

    public static void main(String[] args) {
        LeetCode81 leetCode81 = new LeetCode81();
        System.out.println(leetCode81.search(new int[]{1, 3, 1, 1}, 3));
    }

    public boolean search(int[] nums, int target) {
        if (nums.length == 0)
            return false;
        int min = nums[0], minIndex = 0, length = nums.length;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < min) {
                min = nums[i];
                minIndex = i;
            }
        }
        int left = 0, right = nums.length, mid, realIndex;
        while (left <= right) {
            mid = (left + right) / 2;
            realIndex = (mid + minIndex) % length;
            if (nums[realIndex] < target)
                left = mid + 1;
            else if (nums[realIndex] > target)
                right = mid - 1;
            else
                return true;
        }
        return false;
    }

//------------------------------------------------------------------

    //核心关键就是总有半个分区是有序的
    //1 3 1 1
    public boolean search1(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int start = 0;
        int end = nums.length - 1;
        int mid;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[start] == nums[mid]) {
                start++;
                continue;
            }
            //前半部分有序
            if (nums[start] < nums[mid]) {
                //target在前半部分
                if (nums[mid] > target && nums[start] <= target) {
                    end = mid - 1;
                } else {  //否则，去后半部分找
                    start = mid + 1;
                }
            } else {
                //后半部分有序
                //target在后半部分
                if (nums[mid] < target && nums[end] >= target) {
                    start = mid + 1;
                } else {  //否则，去后半部分找
                    end = mid - 1;

                }
            }
        }
        //一直没找到，返回false
        return false;

    }
}
